(1) Field of the Invention
The present invention relates to the field of error detecting and correcting codes for a computer system.
(2) Prior Art
Digital computers work with binary coded information wherein data is represented in the computer as pieces of information forming electrical high and low states corresponding to logical ones and zeros. In the storage and transmission of these electrical states within a computer system, a variety of problems may cause an electrical state to be altered into its inverse state. To ensure proper performance, it is important to be able to detect these errors and also advantageous to be able to correct such errors. However, in any error checking and correcting scheme there are at least two conflicting priorities. First, the scheme must be as simple and compact as possible so as not to unduly add to the complexity to the system (i.e., the hardware circuitry) or decrease its speed. Second, the scheme should be capable of detecting all expected errors while correcting as many errors as possible.
Numerous examples of error checking and correcting schemes are well-known in the art. One of the simplest is the use of parity bits to detect single bit errors in a stream of data. The use of a single parity bit will detect single bit errors in a code word, but is incapable of correcting single bit errors and cannot detect double bit errors.
To detect multiple errors and/or correct errors, some codes utilize multiple parity (check) bits. When the resulting code is formed of code words which are a subset of the n-tuples over a finite field GF(q) of q symbols, the code is referred to as a "linear code". This patent is concerned with linear codes where q=2.
A linear code can be described in two ways: By its generator matrix G or by its parity matrix H. The general systematic form of these matrices is shown in FIGS. 1(a) and 1(b), respectively. Either matrix defines the set of code words that form the code. The code word length is n=(r+k) bits, where r is the number of check bits and k is the number of data bits. A code is typically specified by the notation: (n, k).
The basic scheme for generating and decoding code words is shown in FIG. 2. As shown, the code word v=(v.sub.0, v.sub.1, . . . v.sub.n-1) is formed by calculating the dot product between the k-bit input data word d=(d.sub.0, d.sub.1, . . . d.sub.k-1) and the generator matrix G. Once the code v has been generated, it is subsequently transmitted between system components (e.g., read out of memory) and must then be decoded in order to determine whether the output data word d'=(d.sub.0 ', d.sub.1 ', . . . , d.sub.k-1 ') contains the same data bits as the input data word d. To determine whether the output data word d' correctly reflects the input data word d, a syndrome s is generated for the code word v. This is done by calculating the dot product between the code word v and the transpose of the G matrix, H, so as to obtain s(v)=(s.sub.0, s.sub.1, . . . , s.sub.n-1)=v.multidot.H. The syndrome is used to classify errors found in the output data word d'. If the syndrome s(v)=0, then it is assumed that there are no data bit errors in the output data word d'. If the syndrome s(v).noteq.0, then errors are detected.
The G matrix represents the operations needed to generate the check bits of a code. The combinational logic to carry out these operations, i.e., to generate the check bits for the input data word d to obtain a systematic code word v, is shown in FIG. 3(a). The H matrix represents the operations needed to generate the syndrome bits of a code. The combinational logic to carry out these operations, i.e., to generate the syndrome bits s for the code word v, is shown in FIG. 3(b).
If a code is capable of correcting errors, the syndrome is used both to classify the error as correctable or uncorrectable, and to identify the output data word positions that are in error. For example, a code can correct single bit errors if all columns of its H matrix are non-zero and distinct. If the syndrome matches any one of these column vectors the error is assumed to be correctable with the error occurring at the bit position corresponding to the match.
A code that is capable of correcting single bit errors and detecting double bit errors is referred to as a (SEC-DED) code. In order for a code to be (SEC-DED) its H matrix must have the following properties: (1) all columns are non-zero and distinct, (2) all columns are of odd weight. With this code, a syndrome of odd weight indicates a single bit correctable error, while an even weight, non-zero syndrome indicates an uncorrectable error.
Linear codes can also be used to detect nibble (4-bit) errors. A code that is capable of correcting single bit errors, detecting double bit errors and detecting single b-bit errors is referred to as a (SEC-DED-SbED) code. Codes for b=4 have received extensive study since they can be used to detect failures in memories constructed from memory devices that are 4-bits wide. For these codes, the columns of the H matrix are arranged to give unique syndrome patterns for the b-bit errors, and are typically not in systematic form.
In order to simplify the encoding and decoding circuitry in the use of linear codes, a class of codes has been defined in which the H matrix is constructed by cyclic shifting (i.e., rotating) the rows of the generator submatrix. These codes are called "rotational codes", and have a symmetry that allows the encoding and decoding circuits to be implemented with identical subcircuits specified by the generating submatrix, each by simply altering the input and output connections, respectively.
The amount of encoding and decoding circuitry required for a linear code can be determined by examining its H matrix. The number of 1's in a row determines the width (i.e., the number of inputs) of each of these circuits. For example, if there are 35 binary 1's in a row i, then the circuit required to compute syndrome bits s.sub.i is a 35-input exclusive OR tree. In addition, the arrangement and nature of the columns in the H matrix determines the complexity of the error classification circuitry.
In terms of well-known conventional codes, there is a linear (72, 64) SEC-DED-SbED code which has a weight of 27 for all rows of H, but this code is not rotational. There is also a (72, 64) SEC-DED-SbED code that is rotational, but the row weight is 31, thereby increasing the complexity of its corresponding circuits. Hence, it would be desirable to provide a (72, 64) SEC-DED-S4ED rotational error correction code which has an equal row weight of 27 and a simplified error classification scheme.
It is therefore an object of the present invention to provide a (72, 64) SEC-DED-S4ED error correction code having the following characteristics:
(1) All rows have weight 27 so as to reduce the complexity of the encoding and decoding circuits. PA1 (2) A simple error classification scheme that reduces the complexity of the error classification circuitry. PA1 (3) A rotational property which enables the code to be computed in two halves with the same circuit or to be folded into a (36, 32) burst code.